package com.ls.string;

/**
 * @author liangsu
 * @version v1.0
 * @Description
 * @Date 2021/3/31 16:34
 * @since
 */
public class KMP {

    public int getIndexOf(String s, String m){
        if(s == null || m == null || m.length() < 1 || s.length() < m.length()){
            return -1;
        }

        char[] str = s.toCharArray();
        char[] match = m.toCharArray();

        int[] next = getNextArray(match);

        int x, y;
        x = y = 0;

        while(x < str.length && y < match.length){
            if(str[x] == match[y]){
                x++;
                y++;
            }else if(next[y] == -1){
                x++;
            }else{
                y = next[y];
            }
        }

        return y == match.length ? x - y : -1;
    }

    public int[] getNextArray(char[] match){
        if(match.length == 1){
            return new int[]{-1};
        }

        int[] next = new int[match.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while(i < match.length){
            if(match[i - 1] == match[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[i++] = cn++;
            }
        }

        return next;
    }

    public static void main(String[] args) {
        KMP kmp = new KMP();
//        System.out.println(kmp.getIndexOf("abcdefg", "abc"));
//        System.out.println(kmp.getIndexOf("abcdefg", "bcd"));
//        System.out.println(kmp.getIndexOf("abcdefg", "efg"));
        System.out.println(kmp.getIndexOf("abcdefg", "aaa"));
    }

}
